package leetcode.editor.cn;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.function.BiFunction;

/**
 * @author: yangwk
 * @date: 2023/5/15
 * @description:
 **/
public class P466 {
    public static void main(String[] args) {
        System.out.println(getMaxRepetitions("lovelive", 1000, "lovelive", 999));
    }

    static int[][] dp;

    public static int getMaxRepetitions(String s1, int n1, String s2, int n2) {
        String target = contract(s2, n2);
        String from = contract(s1, n1);
        int length = from.length();
        dp = new int[length + 1][length + 1];
        return getSame(from, 0, length, target);
    }

    static int getSame(String str, int start, int end, String target) {
        int count = 0;
        if (dp[start][end] != 0) {
            return dp[start][end];
        }
        for (int i = start; i < end; i++) {
            for (int j = i + target.length(); j <= end; j++) {
                String substring = str.substring(i, j);
                if (isSame(substring, target)) {
                    count = Math.max(getSame(str, j, end, target) + 1, count);
                }
            }
        }
        dp[start][end] = count;
        return count;
    }

    public static Boolean isSame(String str1, String str2) {
        int m = str1.length();
        int n = str2.length();
        int len1 = str1.length();
        int len2 = str2.length();
        int i = 0, j = 0;
        while (i < len1 && j < len2) {
            if (str1.charAt(i) == str2.charAt(j)) {
                j++;
            }
            i++;
        }
        return j == len2;
    }

    public static String contract(String str, int n) {
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 1; i <= n; i++) {
            stringBuilder.append(str);
        }
        return stringBuilder.toString();
    }
}
